269B - Greenhouse Effect - CodeForces Solution

def read_input():
    a, b = [int(i) for i in input().split()]
    return a, b

def read_list(n):
    lst = [int(input().split()[0]) for _ in range(n)]
    return lst

def calculate_permutations(m, lst):
    perm = (m+1) * [0]
    for i in lst:
        perm[i] = max(perm[1:i+1]) + 1
    return perm

def calculate_difference(perm, n):
    return abs(max(perm) - n)

def main():
    n, m = read_input()
    lst = read_list(n)
    perm = calculate_permutations(m, lst)
    result = calculate_difference(perm, n)
    print(result)

if __name__ == "__main__":
    main()